import java.util.*;

public class AddTwoNumber2 {
    class ListNode{
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    //使用栈模拟
    public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        Stack<Integer> st1 = new Stack<>();
        Stack<Integer> st2 = new Stack<>();
        ListNode cur = l1;
        while(cur != null){
            st1.push(cur.val);
            cur = cur.next;
        }
        cur = l2;
        while(cur != null){
            st2.push(cur.val);
            cur = cur.next;
        }
        ListNode head = null;
        int flag = 0;
        while(!st1.empty() || !st2.empty() || flag != 0){
            int num1 = 0, num2 = 0;
            if(!st1.empty()) num1 = st1.pop();
            if(!st2.empty()) num2 = st2.pop();
            int sum = num1 + num2 + flag;
            flag = sum > 9 ? 1 : 0;
            ListNode tmp = new ListNode(sum % 10);
            tmp.next = head;
            head = tmp;
        }
        return head;
    }

    //反转链表做法
    public ListNode reverseList(ListNode head){
        ListNode cur, prev;
        cur = prev = head;
        head = null;
        while(cur != null){
            cur = cur.next;
            prev.next = head;
            head = prev;
            prev=  cur;
        }
        return head;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        ListNode head = null;
        int flag = 0;
        while(l1 != null || l2 != null || flag != 0){
            int n1 = 0, n2 = 0;
            if(l1 != null) n1 = l1.val;
            if(l2 != null) n2 = l2.val;
            int sum = n1 + n2 + flag;
            flag = sum > 9 ? 1 : 0;
            ListNode tmp = new ListNode(sum % 10);
            tmp.next = head;
            head = tmp;

            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        return head;
    }

    public int matrixSum(int[][] nums) {
        int ans = 0;
        for(int i = 0; i < nums.length; i++){
            Arrays.sort(nums[i]);
        }
        int max = 0;
        for(int i = nums[0].length; i >= 0; i++){
            max = Integer.MIN_VALUE;
            for(int j = 0; j < nums.length; j++){
                max = Math.max(max, nums[j][i]);
            }
            ans += max;
        }
        return ans;
    }
}
